<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <div>
      <p>国风堂&哦漏-知我</p>
      <audio src=".\music\国风堂&哦漏-知我.mp3" autoplay controls></audio>
    </div>
    <div>
      <p>风经过，唱离合-张朕、婉枫</p>
      <audio
        src=".\music\风经过，唱离合-张朕、婉枫.mp3"
        autoplay
        controls
      ></audio>
    </div>
    <div>
      <p>李宗盛-凡人歌</p>
      <audio src=".\music\李宗盛-凡人歌(Live).mp3" autoplay controls></audio>
    </div>
    <div>
      <p>刀郎 - 西海情歌</p>
      <audio src=".\music\刀郎+-+西海情歌.mp3" autoplay controls></audio>
    </div>
    <div>
      <p>李雅 - 越过山丘</p>
      <audio src=".\music\李雅 - 越过山丘 (Live).m4a" autoplay controls></audio>
    </div>
    <div>
      <p>为你我受冷风吹+-+林忆莲</p>
      <audio
        src=".\music\为你我受冷风吹+-+林忆莲.mp3"
        autoplay
        controls
      ></audio>
    </div>
    <div>
      <p>不如回家喝自来水-陈楚生</p>
      <audio
        src=".\music\不如回家喝自来水-陈楚生.mp3"
        autoplay
        controls
      ></audio>
    </div>
    <script>
      window.onload = function () {
        const IsLoop = true

        const audioList = Array.from(document.querySelectorAll('audio'))
        audioList.map((item, i) => {
          item.volume = 0.05
          item.onended = () => {
            if (IsLoop) {
              item.play()
            } else {
              let j = i === audioList.length - 1 ? 0 : i + 1
              audioList[j].play()
            }
          }
        })
      }

      // 动态规划 (共 8 个)
      const funDT1 = function () {
        let list = [
          [1, 1],
          [2, 4],
          [7, 9],
          [6, 10],
          [6, 10],
          [3, 5]
        ]
        list.sort((a, b) => b[1] - a[1])
        console.log(list)
        const resArr = []
        const sumArr = []
        const total = 10
        for (let i = 0; i < list.length; i++) {
          let sum = list[i][0]
          let value = list[i][1]
          let sumStr = '' + sum
          let valueStr = '' + value
          if (sum < total) {
            const otherList = list.slice(i + 1)
            for (const o of otherList) {
              if (sum + o[0] <= total) {
                sum += o[0]
                sumStr = sumStr + '+' + o[0]
                value += o[1]
                valueStr = valueStr + '+' + o[1]
              }
            }
            //   resArr.push(sumStr + '=' + sum + '  ' + valueStr + '=' + value)
            sumArr.push(value)
          }
        }
        //   console.log(resArr)
        console.log(Math.max(...sumArr))
      }

      const funDT2 = function () {
        const maxSum = function (A) {
          // 假设有一个长度为n的数组A，需要从中选出一些数，使得它们的和最大，但是选出的数不能相邻。
          // 思路：动态规划
          // 定义状态      假设到第A[i]个数时 最大和为f(i)
          // 状态转移方程  那么 最大和f(i) 是否包含第i个
          //                  包含第i个  则等于 f(i-2) + A[i]
          //                  不包含第i个 则等于 f(i-1)
          //                  所以最大值 f(i) = max(f(i-2)+A[i],f(i-1))
          // 边界条件      f[-1] = 0
          //              f(0) = A[0]
          //              f(1) = max(f[-1] + A[1], f[0])
          // 顺序计算      f(2) = max(f[0] + A[2], f[1])
          //              ...
          const n = A.length
          if (n === 0) {
            return 0
          } else if (n === 1) {
            return A[0]
          } else {
            const f = new Array(n)
            f[-1] = 0
            f[0] = A[0]
            for (let i = 1; i < n; i++) {
              f[i] = Math.max(f[i - 2] + A[i], f[i - 1])
            }
            console.log(f)
            return f[n - 1]
          }
        }
        let arr = [1, 2, 4, 1, 7, 8, 3]
        const res = maxSum(arr)
        console.log(res)
      }

      const funDT3 = function () {
        const getTotal = (N) => {
          // 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
          // 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
          // 思路：动态规划
          // dp[n] 表示上n阶楼梯的走法总数
          // dp[n] 当有n阶楼梯时 等于 最后一次上1个台阶（dp(n-1)）+ 最后一次上2个台阶（dp(n-2)）
          // dp[n] = dp[n-1] + dp[n-2]
          // 斐波那契数列
          const dp = []
          dp[0] = 1
          dp[1] = 1
          for (let i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + dp[i - 2]
          }
          console.log(dp)
          return dp[N]
        }

        const n = 10
        const total = getTotal(10)
        console.log(total)
      }

      const funDT4 = function () {
        // 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。
        // 一旦你支付此费用，即可选择向上爬一个或者两个台阶。
        // 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
        // 请你计算并返回达到楼梯顶部的最低花费。

        // 示例 1
        // 输入：cost = [10, 15, 20]
        // 输出：15
        // 解释：你将从下标为 1 的台阶开始。
        // - 支付 15 ，向上爬两个台阶，到达楼梯顶部。
        // 总花费为 15 。

        // 示例 2
        // 输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
        // 输出：6
        // 解释：你将从下标为 0 的台阶开始。
        // - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
        // - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
        // - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
        // - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
        // - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
        // - 支付 1 ，向上爬一个台阶，到达楼梯顶部。
        // 总花费为 6 。

        const minSum = (cost) => {
          const n = cost.length
          const dp = []
          dp[0] = 0
          dp[1] = cost[0]
          for (let i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i - 1]
          }

          console.log(dp)
          return dp[n]
        }
        let arr = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
        const res = minSum(arr)
        console.log(res)
      }

      const funDT5 = function () {
        // 你有三种硬币，2元、5元、7元，每种硬币足够多，买一本书需要27元，用最少的硬币组合
        // 假设 一共用了 k枚硬币  A(27) = k
        // A(27 - 2) + 1 = k
        // A(27 - 5) + 1 = k
        // A(27 - 7) + 1 = k
        // 最优解是 A(27) = min[A(27 - 2), A(27 - 5), A(27 - 7)] + 1 = k
        // 状态方程 A(f) = min[A(f - 2), A(f - 5), A(f - 7)] + 1
        // 状态方程 可以换一种表达方式 为
        // A(f) = '无穷大'
        // list = [2, 5, 7]
        // for (let j = 0; j < list.length; j++) {
        //   A(f) = min(A[f - list[j]] + 1, A(f))
        // }
        const fn = (money) => {
          const coins = [2, 5, 7]
          const f = []
          f[0] = 0
          for (let i = 1; i <= money; i++) {
            f[i] = Infinity
            for (let j = 0; j < coins.length; j++) {
              if (i >= coins[j] && f[i - coins[j]] !== Infinity) {
                f[i] = Math.min(f[i - coins[j]] + 1, f[i])
              }
            }
          }
          console.log(f)
          return f[money]
        }
        const money = 27
        const res = fn(money)
        console.log(res)
      }

      const funDT6 = function () {
        // 一个机器人位于一个 m x n 网格的左上角 （起始点在0 x 0 ）。
        // 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。
        // 问总共有多少条不同的路径？
        const fn = (m, n) => {
          const mn = []
          for (let i = 0; i < m; i++) {
            mn[i] = []
            for (let j = 0; j < n; j++) {
              mn[i][j] = 0
            }
          }
          for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
              if (i === 0 || j === 0) {
                mn[i][j] = 1
              } else {
                mn[i][j] = mn[i - 1][j] + mn[i][j - 1]
              }
            }
          }
          console.log(mn)
          return mn[m - 1][n - 1]
        }

        const res = fn(2, 3)
        console.log(res)
      }

      const funDT7 = function () {
        // 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
        // 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
        // 输出：6
        // 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
        function fn(arr) {
          // 动态规划
          // dp[i] 表示以第i个元素结尾的最大和
          // 当 dp[i-1]<0时 dp[i - 1] + arr[i] 必定 小于 arr[i]
          // 状态方程 dp[i] = max(dp[i - 1] + arr[i], arr[i])
          const n = arr.length
          const dp = []
          dp[0] = arr[0]
          for (let i = 1; i < n; i++) {
            dp[i] = Math.max(dp[i - 1] + arr[i], arr[i])
          }

          console.log(dp)
          return Math.max(...dp)
        }
        // const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
        const nums = [4, -1, 2, 1]
        const res = fn(nums)
        console.log(res)
      }
      
      const funDT8 = function () {
        // 小R正在计划一次从地点A到地点B的徒步旅行，总路程需要 N 天。
        // 为了在旅途中保持充足的能量，小R每天必须消耗1份食物。
        // 幸运的是，小R在路途中每天都会经过一个补给站，可以购买食物进行补充。
        // 然而，每个补给站的食物每份的价格可能不同，并且小R最多只能同时携带 K 份食物。
        // 现在，小R希望在保证每天都有食物的前提下，以最小的花费完成这次徒步旅行。
        // 你能帮助小R计算出最低的花费是多少吗？

        function fn(n, k, data) {
          const dp = []

          // 第一天 必须买
          dp[0] = data[0]

          for (let i = 1; i <= n; i++) {
            // 判断吃当天的 还是吃前几天（i-1天...i-k天）买的   哪个最省钱选哪个
            dp[i] = dp[i - 1] + data[i]
            for (let j = i - 1; j > i - k && j >= 0; j--) {
              dp[i] = Math.min(dp[i], dp[i - 1] + data[j])
            }
          }

          console.log(dp)
          return dp[n - 1]
        }

        // 添加测试用例
        console.log(solution(5, 2, [1, 2, 3, 3, 2]) === 9)
        console.log(solution(6, 3, [4, 1, 5, 2, 1, 3]) === 9)
        console.log(solution(4, 1, [3, 2, 4, 1]) === 10)
      }

      // 排序 (共 2 个)
      const funPX1 = function () {
        // 冒泡
        function fn(arr) {
          for (let i = 0; i < arr.length; i++) {
            for (let j = 0; j < arr.length; j++) {
              if (arr[i] < arr[j]) {
                let temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp
              }
            }
          }
          return arr
        }
        let arr = [1, 10, 5, 8, 4, 6, 3, 7, 2, 5, 0]
        const res = fn(arr)
        console.log(res)
      }

      const funPX2 = function () {
        // 插入排序
        function fn(arr) {
          for (let i = 1; i < arr.length; i++) {
            let temp = arr[i]
            let j = i - 1
            while (j >= 0 && arr[j] > temp) {
              arr[j + 1] = arr[j]
              j--
            }
            arr[j + 1] = temp
          }
          return arr
        }
        let arr = [1, 10, 5, 8, 4, 6, 3, 7, 2, 5, 0]
        const res = fn(arr)
        console.log(res)
      }

      // 双指针 (共 1 个)
      const funSZZ1 = function () {
        // 输入：["h","e","l","l","o"]
        // 输出：["o","l","l","e","h"]
        function fn(list) {
          let i = -1
          let j = list.length
          while (i++ < j--) {
            ;[list[i], list[j]] = [list[j], list[i]]
          }
          return list
        }
        const arr = ['h', 'e', 'l', 'l', 'o']
        const res = fn(arr)
        console.log(res)
      }

      // LRU  与  LFU (共 1 个)
      // 举一个简单的例子：缓存中有 A、B 两个数据，且已达到上限，
      // 如果 数据 A 先被访问了 10 次，
      // 然后 数据 B 被访问 1 次，
      // 当存入新的 数据 C 时，
      // 如果当前是 LRU 算法，会将 数据 A 淘汰，
      // 而如果是 LFU 算法，则会淘汰 数据 B。

      // 简单来说，
      // 就是在 LRU 算法中，不管访问的频率，只要最近访问过，就不会将这个数据淘汰，
      // 而在 LFU 算法中，将访问的频率作为权重，只要访问频率越高，该数据就越不会被淘汰，即使该数据很久没有被访问过。

      // https://www.51cto.com/article/704616.html
      const funLL1 = function () {
        // LRU 缓存算法是一种常用的内存管理算法，用于置换最近最少使用的缓存数据
        // 这个实现包括了LRU算法的基本操作：get和put。
        // 在put操作中，
        // 如果键已存在于缓存中，它将被删除并重新插入到缓存的尾部。
        // 如果缓存已满，它将删除最老的键，并将新的键值对添加到缓存的尾部。
        class LRUCache {
          constructor(capacity) {
            // capacity  最大缓存能力
            this.capacity = capacity
            this.cache = new Map()
            this.size = 0
          }

          get(key) {
            if (this.cache.has(key)) {
              const value = this.cache.get(key)
              this.cache.delete(key)
              this.cache.set(key, value)
              return value
            }
            return -1 // 或者其他标识符表示未找到
          }

          set(key, value) {
            if (this.cache.has(key)) {
              this.cache.delete(key)
            } else if (this.size >= this.capacity) {
              this.cache.delete(this.cache.keys().next().value) //https://blog.csdn.net/weixin_44525145/article/details/138053015
              this.size--
            }
            this.cache.set(key, value)
            this.size++
          }
        }

        // // 使用示例
        // const cache = new LRUCache(2)

        // cache.set('key1', 'value1')
        // cache.set('key2', 'value2')
        // console.log(cache.get('key1')) // 返回 'value1'

        // cache.set('key3', 'value3')
        // console.log(cache.get('key2')) // 返回 -1 (未找到), 因为 'key2' 在put('key3', 'value3')时被替换了

        // cache.set('key4', 'value4')
        // console.log(cache.get('key1')) // 返回 -1 (未找到), 因为 'key1' 在put('key3', 'value3')和put('key4', 'value4')中都被访问过，但它是最近最少使用的

        // console.log(cache.get('key3')) // 返回 'value3'
        // console.log(cache.get('key4')) // 返回 'value4'
      }
    </script>
  </body>
</html>
